The present invention relates, in general, to measuring and testing and, in particular, to frequency spectrum analyzer by Fourier analysis.
A classic problem in signal analysis is detecting weak tones in noise and estimating the frequency of the tone.
The most common method used in frequency estimation is the Fourier transform. However, the Fourier transform cannot resolve signals that are separated by less than the width of one transform cell.
Other common methods of frequency estimation are based on phase differentiation of the signal. These methods fail if more than one signal is present. This is because the differential phase is derived from the sum of the signal components.
A cross spectral method provides a very accurate frequency estimate in severe noise, but cannot resolve two signals which are not already separated by the Fourier transform on which the method is based.
In a typical two-dimensional Fourier analysis, a signal is sampled to form a first matrix of rows and columns, where each column represents a time segment of data. A Fast Fourier Transform (FFT) is performed on the columns of the first matrix to form a second matrix. The rows of the second matrix represent frequency and the columns represent time. That is, each row in the second matrix is a time-indexed vector, representing the time-varying spectral response of the signal at the frequency represented by the row. A second FFT is then performed on the rows of the second matrix.
In an FFT method known as the Large FFT method, a sufficient amount of data is selected from a signal of interest to form a vector, an FFT is computed for the vector, the magnitude of each element in the FFT is determined, and the element with the peak magnitude is used to estimate the frequency of the signal.
In an FFT method known as the Welch""s method, a signal is sampled to form a first matrix of rows and columns. An FFT is performed on the columns of the first matrix to form a second matrix. Each entry in the second matrix is replaced with its absolute value. The rows of the second matrix are then summed. The highest sum (i.e., the peak) is selected.
In an FFT method known as the Cross-Power Spectrum method, a signal is sampled to form a first matrix of rows and columns. The signal is then delayed a user-definable period of time. The delayed signal is then sampled to form a second matrix of rows and columns. An FFT is performed on the columns of the first matrix. An FFT is performed on the columns of the second matrix. The results of the two FFTs are multiplied together to form a third matrix. The third matrix is averaged. An amplitude and phase are computed from the averaged matrix. Determine the peak amplitude and calculate the frequency corresponding thereto. The phase of the signal is estimated as being located where the peak amplitude occurs. The frequency of the signal is estimated by interpolation as follows:
Fest=Fp+(PHI(i1, i2, . . . , in))/(2xc3x97xcfx80xc3x97DELAY), 
where
Fest is the estimated signal frequency,
PHI is the estimated phase,
DELAY is the time by which the signal was delayed; and
Fp is the estimated frequency.
U.S. Pat. No. 4,904,930, entitled xe2x80x9cMETHOD OF CARRIER FREQUENCY ESTIMATIONxe2x80x9d; U.S. Pat. No. 5,165,051, entitled xe2x80x9cMODIFIED FAST FREQUENCY ACQUISITION VIA ADAPTIVE LEAST SQUARES ALGORITHMxe2x80x9d; U.S. Pat. No. 5,293,114, entitled xe2x80x9cFREQUENCY MEASUREMENT RECEIVER WITH MEANS TO RESOLVE AN AMBIGUITY IN MULTIPLE FREQUENCY ESTIMATIONxe2x80x9d; U.S. Pat. No. 5,640,431, entitled xe2x80x9cMETHOD AND APPARATUS FOR OFFSET FREQUENCY ESTIMATION FOR A COHERENT RECEIVERxe2x80x9d; U.S. Pat. No. 5,729,124, entitled xe2x80x9cESTIMATION OF SIGNAL FREQUENCY USING FAST WALSH TRANSFORMxe2x80x9d; and U.S. Pat. No. 6,218,896, entitled xe2x80x9cVECTORED DEMODULATION AND FREQUENCY ESTIMATION APPARATUS AND METHOD,xe2x80x9d each disclose a device for or method of estimating frequency, but none of these patents disclose the device for and method of estimating frequency of the present invention. U.S. Pat. Nos. 4,904,930; 5,165,051; 5,293,114; 5,640,431; 5,729,124; and 6,218,896 are hereby incorporated by reference into the specification of the present invention.
It is an object of the present invention to estimate the frequency of a signal.
It is another object of the present invention to estimate the frequency of a signal using multi-dimensional Fast Fourier Transforms (FFTs).
The present invention is a method of estimating the frequency of a signal using multidimensional Fast Fourier Transforms, where the first step of the method is receiving a signal for which its frequency is to be determined.
If the received signal is not in the form of a row vector then the second step is converting the received signal to a row vector.
The third step of the method is segmenting the row vector into a plurality of segmented row vectors.
The fourth step of the method is converting each of the plurality of segmented row vectors to a first matrix.
The fifth step of the method is multiplying each entry in the first matrix by a first weighting column-vector.
The sixth step of the method is performing a Fourier transform on each result of the fifth step.
The seventh step of the method is delaying the received signal by a user-definable period of time.
If the delayed signal is not in the form of a row vector then the eighth step of the method is converting the delayed signal into a delayed row vector.
The ninth step of the method is segmenting the delayed row vector into a plurality of segmented delayed row vectors.
The tenth step of the method is converting each of the plurality of segmented delayed row vectors to a second matrix.
The eleventh step of the method is multiplying each entry in the second matrix by a second weighting column-vector.
The twelfth step of the method is performing a Fourier transform on each result of the eleventh step.
The thirteenth step of the method is calculating the complex conjugate of each result of the twelfth step.
The fourteenth step of the method is forming a cross-spectrum matrix by multiplying each result of the sixth step by the corresponding complex conjugate calculated in the thirteenth step, where each entry in the cross-spectrum matrix includes a magnitude and a phase.
The fifteenth step of the method is selecting at least one magnitude entry in the cross-spectrum matrix that is above a user-definable threshold. In the preferred embodiment, the user-definable threshold is the average of the magnitude entries in the cross-spectrum matrix.
The sixteenth step of the method is setting an angular frequency of the signal equal to the phase of an entry in the cross-spectrum matrix that corresponds to the at least one entry selected in the fifteenth step.
The seventeenth step of the method is determining the frequency of each entry in the cross-spectrum matrix corresponding to the at least one entry selected in the fifteenth step as the corresponding estimated angular frequency divided by the product of 2xcfx80 and the time delay of the seventh step and proceeding to the next step if another row of the second matrix is desired to be processed, otherwise stopping.
The eighteenth step of the method is selecting a user-definable row from the second matrix as the row vector and returning to the third step for additional processing.